home *** CD-ROM | disk | FTP | other *** search
/ Speccy ClassiX 1998 / Speccy ClassiX 98.iso / amiga_system / the_aminet / dev / gcc / ixemulsrc.lha / ixemul-41.4 / gen_library / fts.c < prev    next >
C/C++ Source or Header  |  1995-05-28  |  22KB  |  801 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #if defined(LIBC_SCCS) && !defined(lint)
  35. static char sccsid[] = "@(#)fts.c    5.19 (Berkeley) 5/9/91";
  36. #endif /* LIBC_SCCS and not lint */
  37.  
  38. #define KERNEL
  39. #include "ixemul.h"
  40. #include "kprintf.h"
  41.  
  42. static inline int max (int a, int b) { return a < b ? a : b; }
  43.  
  44. #include <sys/cdefs.h>
  45. #include <fcntl.h>
  46. #include <dirent.h>
  47. #include "fts.h"
  48. #include <stdlib.h>
  49. #include <string.h>
  50. #include <unistd.h>
  51.  
  52. static FTSENT *fts_alloc(), *fts_build(), *fts_sort();
  53. static void fts_load(), fts_lfree();
  54. static u_short fts_stat();
  55. static char *fts_path();
  56.  
  57. #define    ISSET(opt)    (sp->fts_options & opt)
  58. #define    SET(opt)    (sp->fts_options |= opt)
  59.  
  60. #define    CHDIR(sp, path)    (!ISSET(FTS_NOCHDIR) && chdir(path))
  61. #define    FCHDIR(sp, fd)    (!ISSET(FTS_NOCHDIR) && fchdir(fd))
  62.  
  63. /* fts_build flags */
  64. #define    BCHILD        1        /* from fts_children */
  65. #define    BREAD        2        /* from fts_read */
  66.  
  67. FTS *
  68. fts_open(argv, options, compar)
  69.     char * const *argv;
  70.     register int options;
  71.     int (*compar)();
  72. {
  73.     register FTS *sp;
  74.     register FTSENT *p, *root;
  75.     register int nitems, maxlen;
  76.     FTSENT *parent, *tmp;
  77.     int len;
  78.  
  79.     /* Allocate/initialize the stream */
  80.     if (!(sp = (FTS *)malloc((u_int)sizeof(FTS))))
  81.         return(NULL);
  82.     bzero(sp, sizeof(FTS));
  83.     sp->fts_compar = compar;
  84.     sp->fts_options = options;
  85.  
  86.     /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
  87.     if (ISSET(FTS_LOGICAL))
  88.         SET(FTS_NOCHDIR);
  89.  
  90.     /* Allocate/initialize root's parent. */
  91.     if (!(parent = fts_alloc(sp, "", 0)))
  92.         goto mem1;
  93.     parent->fts_level = FTS_ROOTPARENTLEVEL;
  94.  
  95.     /* Allocate/initialize root(s). */
  96.     maxlen = -1;
  97.     for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
  98.         if (!(len = strlen(*argv))) {
  99.             errno = ENOENT;
  100.             KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  101.             goto mem2;
  102.         }
  103.         if (maxlen < len)
  104.             maxlen = len;
  105.         p = fts_alloc(sp, *argv, len);
  106.         p->fts_level = FTS_ROOTLEVEL;
  107.         p->fts_parent = parent;
  108.         /*
  109.          * If comparison routine supplied, traverse in sorted
  110.          * order; otherwise traverse in the order specified.
  111.          */
  112.         if (compar) {
  113.             p->fts_link = root;
  114.             root = p;
  115.             p->fts_accpath = p->fts_name;
  116.             if (!(options & FTS_NOSTAT))
  117.                 p->fts_info = fts_stat(sp, p, 0);
  118.         } else {
  119.             p->fts_link = NULL;
  120.             if (!root)
  121.                 tmp = root = p;
  122.             else {
  123.                 tmp->fts_link = p;
  124.                 tmp = p;
  125.             }
  126.         }
  127.     }
  128.     if (compar && nitems > 1)
  129.         root = fts_sort(sp, root, nitems);
  130.  
  131.     /*
  132.      * Allocate a dummy pointer and make fts_read think that we've just
  133.      * finished the node before the root(s); set p->fts_info to FTS_NS
  134.      * so that everything about the "current" node is ignored.
  135.      */
  136.     if (!(sp->fts_cur = fts_alloc(sp, "", 0)))
  137.         goto mem2;
  138.     sp->fts_cur->fts_link = root;
  139.     sp->fts_cur->fts_info = FTS_NS;
  140.  
  141.     /* Start out with at least 1K+ of path space. */
  142.     if (!fts_path(sp, MAX(maxlen, MAXPATHLEN)))
  143.         goto mem3;
  144.  
  145.     /*
  146.      * If using chdir(2), grab a file descriptor pointing to dot to insure
  147.      * that we can get back here; this could be avoided for some paths,
  148.      * but almost certainly not worth the effort.  Slashes, symbolic links,
  149.      * and ".." are all fairly nasty problems.  Note, if we can't get the
  150.      * descriptor we run anyway, just more slowly.
  151.      */
  152.     if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)
  153.         SET(FTS_NOCHDIR);
  154.  
  155.     return(sp);
  156.  
  157. mem3:    free(sp->fts_cur);
  158. mem2:    fts_lfree(root);
  159.     free(parent);
  160. mem1:    free(sp);
  161.     return(NULL);
  162. }
  163.  
  164. static void
  165. fts_load(sp, p)
  166.     FTS *sp;
  167.     register FTSENT *p;
  168. {
  169.     register int len;
  170.     register char *cp;
  171.  
  172.     /*
  173.      * Load the stream structure for the next traversal.  Since we don't
  174.      * actually enter the directory until after the preorder visit, set
  175.      * the fts_accpath field specially so the chdir gets done to the right
  176.      * place and the user can access the first node.
  177.      */
  178.     len = p->fts_pathlen = p->fts_namelen;
  179.     bcopy(p->fts_name, sp->fts_path, len + 1);
  180.     if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
  181.         len = strlen(++cp);
  182.         bcopy(cp, p->fts_name, len + 1);
  183.         p->fts_namelen = len;
  184.     }
  185.     p->fts_accpath = p->fts_path = sp->fts_path;
  186.  
  187.     p->fts_info = fts_stat(sp, p, 0);
  188.     sp->rdev = p->fts_statb.st_dev;
  189. }
  190.  
  191. fts_close(sp)
  192.     FTS *sp;
  193. {
  194.     register FTSENT *freep, *p;
  195.     int saved_errno;
  196.  
  197.     if (sp->fts_cur) {
  198.         /*
  199.          * This still works if we haven't read anything -- the dummy
  200.          * structure points to the root list, so we step through to
  201.          * the end of the root list which has a valid parent pointer.
  202.          */
  203.         for (p = sp->fts_cur; p->fts_level > FTS_ROOTPARENTLEVEL;) {
  204.             freep = p;
  205.             p = p->fts_link ? p->fts_link : p->fts_parent;
  206.             free(freep);
  207.         }
  208.         free(p);
  209.     }
  210.  
  211.     /* Free up child linked list, sort array, path buffer. */
  212.     if (sp->fts_child)
  213.         fts_lfree(sp->fts_child);
  214.     if (sp->fts_array)
  215.         free(sp->fts_array);
  216.     free(sp->fts_path);
  217.  
  218.     /* Return to original directory, save errno if necessary. */
  219.     if (!ISSET(FTS_NOCHDIR)) {
  220.         saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
  221.         (void)close(sp->fts_rfd);
  222.     }
  223.  
  224.     /* Free up the stream pointer. */
  225.     free(sp);
  226.  
  227.     /* Set errno and return. */
  228.     if (!ISSET(FTS_NOCHDIR) && saved_errno) {
  229.         errno = saved_errno;
  230.         KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  231.         return(-1);
  232.     }
  233.     return(0);
  234. }
  235.  
  236. /*
  237.  * Special case a root of "/" so that slashes aren't appended causing
  238.  * paths to be written as "//foo".
  239.  */
  240. #define    NAPPEND(p) \
  241.     (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \
  242.         p->fts_path[0] == '/' ? 0 : p->fts_pathlen)
  243.  
  244. FTSENT *
  245. fts_read(sp)
  246.     register FTS *sp;
  247. {
  248.     register FTSENT *p, *tmp;
  249.     register int instr;
  250.     register char *t;
  251.  
  252.     /* If finished or unrecoverable error, return NULL. */
  253.     if (!sp->fts_cur || ISSET(FTS_STOP))
  254.         return(NULL);
  255.  
  256.     /* Set current node pointer. */
  257.     p = sp->fts_cur;
  258.  
  259.     /* Save and zero out user instructions. */
  260.     instr = p->fts_instr;
  261.     p->fts_instr = FTS_NOINSTR;
  262.  
  263.     /* If used fts_link pointer for cycle detection, restore it. */
  264.     if (sp->fts_savelink) {
  265.         p->fts_link = sp->fts_savelink;
  266.         sp->fts_savelink = NULL;
  267.     }
  268.  
  269.     /* Any type of file may be re-visited; re-stat and re-turn. */
  270.     if (instr == FTS_AGAIN) {
  271.         p->fts_info = fts_stat(sp, p, 0);
  272.         return(p);
  273.     }
  274.  
  275.     /*
  276.      * Following a symlink -- SLNONE test allows application to see
  277.      * SLNONE and recover.
  278.      */
  279.     if (instr == FTS_FOLLOW &&
  280.         (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
  281.         p->fts_info = fts_stat(sp, p, 1);
  282.         return(p);
  283.     }
  284.  
  285.     /* Directory in pre-order. */
  286.     if (p->fts_info == FTS_D) {
  287.         /* If skipped or crossed mount point, do post-order visit. */
  288.         if (instr == FTS_SKIP ||
  289.             ISSET(FTS_XDEV) && p->fts_statb.st_dev != sp->rdev) {
  290.             if (sp->fts_child) {
  291.                 fts_lfree(sp->fts_child);
  292.                 sp->fts_child = NULL;
  293.             }
  294.             p->fts_info = FTS_DP;
  295.             return(p);
  296.         } 
  297.  
  298.         /*
  299.          * Cd to the subdirectory, reading it if haven't already.  If
  300.          * the read fails for any reason, or the directory is empty,
  301.          * the fts_info field of the current node is set by fts_build.
  302.          * If have already read and now fail to chdir, whack the list
  303.          * to make the names come out right, and set the parent state
  304.          * so the application will eventually get an error condition.
  305.          * If haven't read and fail to chdir, check to see if we're
  306.          * at the root node -- if so, we have to get back or the root
  307.          * node may be inaccessible.
  308.          */
  309.         if (sp->fts_child) {
  310.             if (CHDIR(sp, p->fts_accpath)) {
  311.                 p->fts_parent->fts_cderr = errno;
  312.                 for (p = sp->fts_child; p; p = p->fts_link)
  313.                     p->fts_accpath =
  314.                         p->fts_parent->fts_accpath;
  315.             }
  316.         } else if (!(sp->fts_child = fts_build(sp, BREAD))) {
  317.             if ISSET(FTS_STOP)
  318.                 return(NULL);
  319.             if (p->fts_level == FTS_ROOTLEVEL &&
  320.                 FCHDIR(sp, sp->fts_rfd)) {
  321.                 SET(FTS_STOP);
  322.                 return(NULL);
  323.             }
  324.             return(p);
  325.         }
  326.         p = sp->fts_child;
  327.         sp->fts_child = NULL;
  328.         goto name;
  329.     }
  330.  
  331.     /* Move to next node on this level. */
  332. next:    tmp = p;
  333.     if (p = p->fts_link) {
  334.         free(tmp);
  335.  
  336.         /* If reached the top, load the paths for the next root. */
  337.         if (p->fts_level == FTS_ROOTLEVEL) {
  338.             fts_load(sp, p);
  339.             return(sp->fts_cur = p);
  340.         }
  341.  
  342.         /* User may have called fts_set on the node. */
  343.         if (p->fts_instr == FTS_SKIP)
  344.             goto next;
  345.         if (p->fts_instr == FTS_FOLLOW) {
  346.             p->fts_info = fts_stat(sp, p, 1);
  347.             p->fts_instr = FTS_NOINSTR;
  348.         }
  349.  
  350. name:        t = sp->fts_path + NAPPEND(p->fts_parent);
  351.         *t++ = '/';
  352.         bcopy(p->fts_name, t, p->fts_namelen + 1);
  353.         return(sp->fts_cur = p);
  354.     }
  355.  
  356.     /* Move up to the parent node. */
  357.     p = tmp->fts_parent;
  358.     free(tmp);
  359.  
  360.     if (p->fts_level == FTS_ROOTPARENTLEVEL) {
  361.         /*
  362.          * Done; free everything up and set errno to 0 so the user
  363.          * can distinguish between error and EOF.
  364.          */
  365.         free(p);
  366.         errno = 0;
  367.         KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  368.         return(sp->fts_cur = NULL);
  369.     }
  370.  
  371.     sp->fts_path[p->fts_pathlen] = '\0';
  372.  
  373.     /*
  374.      * Cd back up to the parent directory.  If at a root node, have to cd
  375.      * back to the original place, otherwise may not be able to access the
  376.      * original node on post-order.
  377.      */
  378.     if (p->fts_level == FTS_ROOTLEVEL) {
  379.         if (FCHDIR(sp, sp->fts_rfd)) {
  380.             SET(FTS_STOP);
  381.             return(NULL);
  382.         }
  383.     }
  384.     else if (CHDIR(sp, "..")) {
  385.         SET(FTS_STOP);
  386.         return(NULL);
  387.     }
  388.  
  389.     /* 
  390.      * If had a chdir error when trying to get into the directory, set the
  391.      * info field to reflect this, and restore errno.  The error indicator
  392.      * has to be reset to 0 so that if the user does an FTS_AGAIN, it all
  393.      * works.
  394.      */
  395.     if (p->fts_cderr) {
  396.         errno = p->fts_cderr;
  397.         KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  398.         p->fts_cderr = 0;
  399.         p->fts_info = FTS_ERR;
  400.     } else
  401.         p->fts_info = FTS_DP;
  402.     return(sp->fts_cur = p);
  403. }
  404.  
  405. /*
  406.  * Fts_set takes the stream as an argument although it's not used in this
  407.  * implementation; it would be necessary if anyone wanted to add global
  408.  * semantics to fts using fts_set.  An error return is allowed for similar
  409.  * reasons.
  410.  */
  411. /* ARGSUSED */
  412. fts_set(sp, p, instr)
  413.     FTS *sp;
  414.     FTSENT *p;
  415.     int instr;
  416. {
  417.     p->fts_instr = instr;
  418.     return(0);
  419. }
  420.  
  421. FTSENT *
  422. fts_children(sp)
  423.     register FTS *sp;
  424. {
  425.     register FTSENT *p;
  426.     int fd;
  427.  
  428.     /* Set current node pointer. */
  429.     p = sp->fts_cur;
  430.  
  431.     /*
  432.      * Set errno to 0 so that user can tell the difference between an
  433.      * error and a directory without entries.  If not a directory being
  434.      * visited in *pre-order*, or we've already had fatal errors, return
  435.      * immediately.
  436.      */
  437.     errno = 0;
  438.     KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  439.     if (ISSET(FTS_STOP) || p->fts_info != FTS_D && p->fts_info != FTS_DNR)
  440.         return(NULL);
  441.  
  442.     /* Free up any previous child list. */
  443.     if (sp->fts_child)
  444.         fts_lfree(sp->fts_child);
  445.  
  446.     /*
  447.      * If using chdir on a relative path and called BEFORE fts_read does
  448.      * its chdir to the root of a traversal, we can lose -- we need to
  449.      * chdir into the subdirectory, and we don't know where the current
  450.      * directory is, so we can't get back so that the upcoming chdir by
  451.      * fts_read will work.
  452.      */
  453.     if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
  454.         ISSET(FTS_NOCHDIR))
  455.         return(sp->fts_child = fts_build(sp, BCHILD));
  456.  
  457.     if ((fd = open(".", O_RDONLY, 0)) < 0)
  458.         return(NULL);
  459.     sp->fts_child = fts_build(sp, BCHILD);
  460.     if (fchdir(fd))
  461.         return(NULL);
  462.     (void)close(fd);
  463.     return(sp->fts_child);
  464. }
  465.  
  466. /*
  467.  * This is the tricky part -- do not casually change *anything* in here.  The
  468.  * idea is to build the linked list of entries that are used by fts_children
  469.  * and fts_read.  There are lots of special cases.
  470.  *
  471.  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
  472.  * set and it's a physical walk (so that symbolic links can't be directories),
  473.  * we assume that the number of subdirectories in a node is equal to the number
  474.  * of links to the parent.  This allows stat calls to be skipped in any leaf
  475.  * directories and for any nodes after the directories in the parent node have
  476.  * been found.  This empirically cuts the stat calls by about 2/3.
  477.  */
  478. #define    ISDOT(a)    (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2]))
  479.  
  480. static FTSENT *
  481. fts_build(sp, type)
  482.     register FTS *sp;
  483.     int type;
  484. {
  485.     register struct dirent *dp;
  486.     register FTSENT *p, *head;
  487.     register int nitems;
  488.     FTSENT *cur;
  489.     DIR *dirp;
  490.     int cderr, descend, len, level, maxlen, nlinks, saved_errno;
  491.     char *cp;
  492.     extern DIR *opendir (char *);
  493.     extern struct dirent *readdir (DIR *);
  494.  
  495.     /* Set current node pointer. */
  496.     cur = sp->fts_cur;
  497.  
  498.     /*
  499.      * Open the directory for reading.  If this fails, we're done.
  500.      * If being called from fts_read, set the fts_info field.
  501.      */
  502.     if (!(dirp = opendir(cur->fts_accpath))) {
  503.         if (type == BREAD)
  504.             cur->fts_info = FTS_DNR;
  505.         return(NULL);
  506.     }
  507.  
  508.     /*
  509.      * Nlinks is the number of possible entries of type directory in the
  510.      * directory if we're cheating on stat calls, 0 if we're not doing
  511.      * any stat calls at all, -1 if we're doing stats on everything.
  512.      */
  513.     nlinks =
  514.         ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ?
  515.         cur->fts_statb.st_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1;
  516.  
  517.     /*
  518.      * If we're going to need to stat anything or we want to descend
  519.      * and stay in the directory, chdir.  If this fails we keep going.
  520.      * We won't be able to stat anything, but we can still return the
  521.      * names themselves.  Note, that since fts_read won't be able to
  522.      * chdir into the directory, it will have to return different path
  523.      * names than before, i.e. "a/b" instead of "b".  Since the node
  524.      * has already been visited in pre-order, have to wait until the
  525.      * post-order visit to return the error.  This is all fairly nasty.
  526.      * If a program needed sorted entries or stat information, they had
  527.      * better be checking FTS_NS on the returned nodes.
  528.      */
  529.     if (nlinks || type == BREAD)
  530.         if (FCHDIR(sp, dirfd(dirp))) {
  531.             if (type == BREAD)
  532.                 cur->fts_cderr = errno;
  533.             descend = nlinks = 0;
  534.             cderr = 1;
  535.         } else {
  536.             descend = 1;
  537.             cderr = 0;
  538.         }
  539.     else
  540.         descend = 0;
  541.  
  542.     /*
  543.      * Figure out the max file name length that can be stored in the
  544.      * current path -- the inner loop allocates more path as necessary.
  545.      * We really wouldn't have to do the maxlen calculations here, we
  546.      * could do them in fts_read before returning the path, but it's a
  547.      * lot easier here since the length is part of the dirent structure.
  548.      *
  549.      * If not changing directories set a pointer so that we can just
  550.      * append each new name into the path.
  551.      */
  552.     maxlen = sp->fts_pathlen - cur->fts_pathlen - 1;
  553.     len = NAPPEND(cur);
  554.     if (ISSET(FTS_NOCHDIR)) {
  555.         cp = sp->fts_path + len;
  556.         *cp++ = '/';
  557.     }
  558.  
  559.     level = cur->fts_level + 1;
  560.  
  561.     /* Read the directory, attaching each entry to the `link' pointer. */
  562.     for (head = NULL, nitems = 0; dp = readdir(dirp);) {
  563.         if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
  564.             continue;
  565.  
  566.         if (!(p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)))
  567.             goto mem1;
  568.         if (dp->d_namlen > maxlen) {
  569.             if (!fts_path(sp, (int)dp->d_namlen)) {
  570.                 /*
  571.                  * No more memory for path or structures.  Save
  572.                  * errno, free up the current structure and the
  573.                  * structures already allocated.
  574.                  */
  575. mem1:                saved_errno = errno;
  576.                 if (p)
  577.                     free(p);
  578.                 fts_lfree(head);
  579.                 (void)closedir(dirp);
  580.                 errno = saved_errno;
  581.                   KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  582.                 cur->fts_info = FTS_ERR;
  583.                 SET(FTS_STOP);
  584.                 return(NULL);
  585.             }
  586.             maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
  587.         }
  588.  
  589.         p->fts_pathlen = len + dp->d_namlen + 1;
  590.         p->fts_parent = sp->fts_cur;
  591.         p->fts_level = level;
  592.  
  593.         if (nlinks) {
  594.             /* Build a file name for fts_stat to stat. */
  595.             if (ISSET(FTS_NOCHDIR)) {
  596.                 p->fts_accpath = p->fts_path;
  597.                 bcopy(p->fts_name, cp, p->fts_namelen + 1);
  598.             } else
  599.                 p->fts_accpath = p->fts_name;
  600.             p->fts_info = fts_stat(sp, p, 0);
  601.             if (nlinks > 0 && p->fts_info == FTS_D)
  602.                 --nlinks;
  603.         } else if (cderr) {
  604.             p->fts_info = ISSET(FTS_NOSTAT) ? FTS_NSOK : FTS_NS;
  605.             p->fts_accpath = cur->fts_accpath;
  606.         } else {
  607.             p->fts_accpath =
  608.                 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
  609.             p->fts_info = FTS_NSOK;
  610.         }
  611.  
  612.         p->fts_link = head;
  613.         head = p;
  614.         ++nitems;
  615.     }
  616.     (void)closedir(dirp);
  617.  
  618.     /*
  619.      * If not changing directories, reset the path back to original
  620.      * state.
  621.      */
  622.     if (ISSET(FTS_NOCHDIR)) {
  623.         if (cp - 1 > sp->fts_path)
  624.             --cp;
  625.         *cp = '\0';
  626.     }
  627.  
  628.     /*
  629.      * If descended after called from fts_children or called from
  630.      * fts_read and didn't find anything, get back.  If can't get
  631.      * back, we're done.
  632.      */
  633.     if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) {
  634.         cur->fts_info = FTS_ERR;
  635.         SET(FTS_STOP);
  636.         return(NULL);
  637.     }
  638.  
  639.     /* If we didn't find anything, just do the post-order visit */
  640.     if (!nitems) {
  641.         if (type == BREAD)
  642.             cur->fts_info = FTS_DP;
  643.         return(NULL);
  644.     }
  645.  
  646.     /* Sort the entries. */
  647.     if (sp->fts_compar && nitems > 1)
  648.         head = fts_sort(sp, head, nitems);
  649.     return(head);
  650. }
  651.  
  652. static u_short
  653. fts_stat(sp, p, follow)
  654.     FTS *sp;
  655.     register FTSENT *p;
  656.     int follow;
  657. {
  658.     int saved_errno;
  659.  
  660.     /*
  661.      * If doing a logical walk, or application requested FTS_FOLLOW, do
  662.      * a stat(2).  If that fails, check for a non-existent symlink.  If
  663.      * fail, return the errno from the stat call.
  664.      */
  665.     if (ISSET(FTS_LOGICAL) || follow) {
  666.         if (stat(p->fts_accpath, &p->fts_statb)) {
  667.             saved_errno = errno;
  668.             if (!lstat(p->fts_accpath, &p->fts_statb)) {
  669.                 errno = 0;
  670.                   KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  671.                 return(FTS_SLNONE);
  672.             } 
  673.             errno = saved_errno;
  674.             KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  675.             bzero(&p->fts_statb, sizeof(struct stat));
  676.             return(FTS_NS);
  677.         }
  678.     } else if (lstat(p->fts_accpath, &p->fts_statb)) {
  679.         bzero(&p->fts_statb, sizeof(struct stat));
  680.         return(FTS_NS);
  681.     }
  682.  
  683.     /*
  684.      * Cycle detection is done as soon as we find a directory.  Detection
  685.      * is by brute force; if the tree gets deep enough or the number of
  686.      * symbolic links to directories high enough something faster might
  687.      * be worthwhile.
  688.      */
  689.     if (S_ISDIR(p->fts_statb.st_mode)) {
  690.         register FTSENT *t;
  691.         register dev_t dev;
  692.         register ino_t ino;
  693.  
  694.         dev = p->fts_statb.st_dev;
  695.         ino = p->fts_statb.st_ino;
  696.         for (t = p->fts_parent; t->fts_level > FTS_ROOTLEVEL;
  697.             t = t->fts_parent)
  698.             if (ino == t->fts_statb.st_ino &&
  699.                 dev == t->fts_statb.st_dev) {
  700.                 sp->fts_savelink = p->fts_link;
  701.                 p->fts_link = t;
  702.                 return(FTS_DC);
  703.             }
  704.         return(FTS_D);
  705.     }
  706.     if (S_ISLNK(p->fts_statb.st_mode))
  707.         return(FTS_SL);
  708.     if (S_ISREG(p->fts_statb.st_mode))
  709.         return(FTS_F);
  710.     return(FTS_DEFAULT);
  711. }
  712.  
  713. #define    R(type, nelem, ptr) \
  714.     (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type)))
  715.  
  716. static FTSENT *
  717. fts_sort(sp, head, nitems)
  718.     FTS *sp;
  719.     FTSENT *head;
  720.     register int nitems;
  721. {
  722.     register FTSENT **ap, *p;
  723.  
  724.     /*
  725.      * Construct an array of pointers to the structures and call qsort(3).
  726.      * Reassemble the array in the order returned by qsort.  If unable to
  727.      * sort for memory reasons, return the directory entries in their
  728.      * current order.  Allocate enough space for the current needs plus
  729.      * 40 so we don't realloc one entry at a time.
  730.      */
  731.     if (nitems > sp->fts_nitems) {
  732.         sp->fts_nitems = nitems + 40;
  733.         if (!(sp->fts_array =
  734.             R(FTSENT *, sp->fts_nitems, sp->fts_array))) {
  735.             sp->fts_nitems = 0;
  736.             return(head);
  737.         }
  738.     }
  739.     for (ap = sp->fts_array, p = head; p; p = p->fts_link)
  740.         *ap++ = p;
  741.     qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
  742.     for (head = *(ap = sp->fts_array); --nitems; ++ap)
  743.         ap[0]->fts_link = ap[1];
  744.     ap[0]->fts_link = NULL;
  745.     return(head);
  746. }
  747.  
  748. static FTSENT *
  749. fts_alloc(sp, name, len)
  750.     FTS *sp;
  751.     char *name;
  752.     register int len;
  753. {
  754.     register FTSENT *p;
  755.  
  756.     /*
  757.      * Variable sized structures; the name is the last element so
  758.      * we allocate enough extra space after the structure to store
  759.      * it.
  760.      */
  761.     if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len))))
  762.         return(NULL);
  763.     bcopy(name, p->fts_name, len + 1);
  764.     p->fts_namelen = len;
  765.     p->fts_path = sp->fts_path;
  766.     p->fts_instr = FTS_NOINSTR;
  767.     p->fts_cderr = 0;
  768.     p->fts_number = 0;
  769.     p->fts_pointer = NULL;
  770.     return(p);
  771. }
  772.  
  773. static void
  774. fts_lfree(head)
  775.     register FTSENT *head;
  776. {
  777.     register FTSENT *p;
  778.  
  779.     /* Free a linked list of structures. */
  780.     while (p = head) {
  781.         head = head->fts_link;
  782.         free(p);
  783.     }
  784. }
  785.  
  786. /*
  787.  * Allow essentially unlimited paths; certain programs (find, rm, ls) need to
  788.  * work on any tree.  Most systems will allow creation of paths much longer
  789.  * than MAXPATHLEN, even though the kernel won't resolve them.  Add an extra
  790.  * 128 bytes to the requested size so that we don't realloc the path 2 bytes
  791.  * at a time.
  792.  */
  793. static char *
  794. fts_path(sp, size)
  795.     FTS *sp;
  796.     int size;
  797. {
  798.     sp->fts_pathlen += size + 128;
  799.     return(sp->fts_path = R(char, sp->fts_pathlen, sp->fts_path));
  800. }
  801.